package swardToOffer.method_2_sort_or_find.find;

/**
 * @Author ChanZany
 * @Date 2021/5/26 11:23
 * @Version 1.0
 * 面试题56（一）：数组中只出现一次的两个数字
 * 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序
 * 找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * 分析:题目要求了空间复杂度为1,所以不能用HashTable的方式进行求解
 * 由于题目中说了除两个数字自外,其他的数字都出现了两次,基于异或xor的性质
 * 1. a xor b = b xor a;
 * 2. a xor a = 0
 * 3. a xor 0 = a
 * 可以得知当数组中只有一个数字是出现一次时,该数组的所有元素异或结果必为那个单独的数字
 * a xor a xor b xor b...xor X xor... = X
 * 所以现在的问题就变成了如何分割数组使它分割后的两个数组内部都只有一个once数字
 * 又因为二进制下 a xor b的结果中为1的那一位一定是a与b不相同的位数,如a=001,b=101
 * m = a xor b = 100 ,而 a & 100 = 000 ,b & 100=100,可以发现必有一数a或b与m进行与运算的结果为0
 * 因此我们可以先求出a xor b的结果中为1的位数m,然后基于m与所有数字求异或的结果对数组进行分割
 * while a^b & m == 0: # m 循环左移一位，直到 z & m ！= 0
 * m <<= 1
 * for num in nums:
 * if num & m: x ^= num  # 若 num & m != 0 , 划分至子数组 1 ，执行遍历异或
 * else: y ^= num        # 若 num & m == 0 , 划分至子数组 2 ，执行遍历异或
 * return x, y
 */
public class NumbersAppearOnce {
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, m = 1, n = 0;
        //求出异或结果n
        for (int num : nums) {
            n ^= num;
        }
        //基于n求出位数m
        while ((m & n) == 0) {
            m <<= 1;
        }
        //分组计算
       for (int num:nums){
        if ((num&m)!=0) x^=num;
        else y^=num;
       }
       return new int[]{x,y};
    }
}
